#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int m, n;
    bool hasValidPath(vector<vector<int>> &grid)
    
    {
        m = grid.size(), n = grid[0].size();
        return dfs(grid, 0, 0, 0);
    }
    // d=1是从左走进来
    // d = 2 right, d == 3,up,d == 4 down
    bool dfs(vector<vector<int>> &grid, int i, int j, int d)
    {
        if (i < 0 || j < 0 || i == m || j == n)
            return false;

        if (grid[i][j] == 0)//判断是不是走过
            return false;

        //储存
        int t = grid[i][j];
        if (d == 1 && (t == 2 || t == 4 || t == 6))
            return false; // 从左边走过来
        if (d == 2 && (t == 2 || t == 3 || t == 5))
            return false; // 从右边
        if (d == 3 && (t == 1 || t == 3 || t == 4))
            return false; // up
        if (d == 4 && (t == 1 || t == 5 || t == 6))
            return false; // down
        if (i == m - 1 && j == n - 1)
            return true;
        bool ans = false;//0之后再递归
        
        grid[i][j] = 0;
        if (t == 1)
            ans = dfs(grid, i, j + 1, 1) || dfs(grid, i, j - 1, 2); // 左右走
        else if (t == 2)
            ans = dfs(grid, i + 1, j, 3) || dfs(grid, i - 1, j, 4); // 上下走
        else if (t == 3)
            ans = dfs(grid, i, j - 1, 2) || dfs(grid, i + 1, j, 3); // 左下
        else if (t == 4)
            ans = dfs(grid, i, j + 1, 1) || dfs(grid, i + 1, j, 3); // 右下
        else if (t == 5)
            ans = dfs(grid, i, j - 1, 2) || dfs(grid, i - 1, j, 4); // 左上
        else if (t == 6)
            ans = dfs(grid, i, j + 1, 1) || dfs(grid, i - 1, j, 4); // 右上
        grid[i][j] = t;
        return ans;
    }
};